package com.leetcode;

/**
 * 2472. 不重叠回文子字符串的最大数目 (困难)
 * <p>
 * 给你一个字符串 s 和一个 正 整数 k 。
 * 从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串：
 * 1. 每个子字符串的长度 至少 为 k 。
 * 2. 每个子字符串是一个 回文串 。
 * 返回最优方案中能选择的子字符串的 最大 数目。
 * 子字符串 是字符串中一个连续的字符序列。
 */
public class LeetCode2472 {

    public static void main(String[] arg0) {
        String s = "fttfjofpnpfydwdwdnns";
        int k = 2;
        System.out.println("长度至少为 " + k + " 的回文子字符串数量 = " + maxPalindromes(s, k));
    }

    public static int maxPalindromes(String s, int k) {
        char[] sArr = s.toCharArray();
        int length = sArr.length;
        int[] dp = new int[length + 1];
        for (int i = 0; i < 2 * length - 1; i++) {
            int l = i / 2;
            int r = l + i % 2; // 中心扩展法
            dp[l + 1] = Math.max(dp[l + 1], dp[l]);
            for (; l >= 0 && r < length && sArr[l] == sArr[r]; --l, ++r) {
                if (r - l + 1 >= k) {
                    dp[r + 1] = Math.max(dp[r + 1], dp[l] + 1);
                    break;
                }
            }
        }
        return dp[length];
    }

    /**
     * 校验是否是回文子字符串
     */
    public static boolean isRevertStr(String subStr) {
        boolean isRevertStr = true;
        int subStrLength = subStr.length();
        for (int i = 0; i < subStrLength / 2; i++) {
            if (subStr.charAt(i) != subStr.charAt(subStrLength - 1 - i)) {
                isRevertStr = false;
                break;
            }
        }
        return isRevertStr;
    }

}
